#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data; //排序树嘛
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

TreeNode *bstSearch(TreeNode *T, int data) 
{
    if (!T) return NULL;
    if (data == T->data) return T;
    if (data < T->data) return bstSearch(T->lchild, data);
    if (data > T->data) return bstSearch(T->rchild, data);
}

void bstInsert(TreeNode **T, int data)
{   //递归的想法
    if (!(*T)) {
        //此时到了可以插入的位置
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = data;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
    } else {
        //三种情况   等于排除
        if (data == (*T)->data) return ;
        if (data > (*T)->data) bstInsert(&((*T)->rchild), data);  //data < 
        else bstInsert(&((*T)->lchild), data); //这个else不可省 因为无return;
    }
}

//验证
void preOrder(TreeNode *T)
{
    if (T) {
        printf("%d ", T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

void inOrder(TreeNode *T)
{
    if (T) {
        inOrder(T->lchild);
        printf("%d ", T->data);
        inOrder(T->rchild);
    }
}

int main(void)
{
    TreeNode *T = NULL;
    int nums[6] = {4, 5, 19, 23, 2, 8};
    for (int i = 0; i < 6; i++) {
        bstInsert(&T, nums[i]);
    }
    inOrder(T);
    putchar('\n');
    preOrder(T);
    return 0;
}